package com.example.algorithm.manacher;

/**
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 *  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 *  示例 1：
 *  输入："abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 *
 *  示例 2：
 *  输入："aaa"
 * 输出：6
 * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 */
public class Leetcode647_CountSubstrings {
    public static void main(String[] args) {
        String str = "abccba";
        System.out.println(new Solution().countSubstrings(str));

    }

    static class Solution {

        /**
         * Manacher算法
         * @param s
         * @return
         */
        private int countSubstrings4(String s) {
            int n = s.length();
            // 初始化将s变为可用Manacher算法的字符串
            StringBuffer sb = new StringBuffer("^#");
            for (int i = 0; i < n; ++i) {
                sb.append(s.charAt(i));
                sb.append('#');
            }
            n = sb.length();
            sb.append('$');

            int[] results = new int[n];
            int iMax = 0, rMax = 0, count = 0;
            for (int i = 1; i < n; ++i) {
                // 初始化 results[i]
                results[i] = i <= rMax ? Math.min(rMax - i + 1, results[2 * iMax - i]) : 1;
                // 中心拓展
                while (sb.charAt(i + results[i]) == sb.charAt(i - results[i])) {
                    ++results[i];
                }
                // 动态维护 iMax 和 rMax
                if (i + results[i] - 1 > rMax) {
                    iMax = i;
                    rMax = i + results[i] - 1;
                }
                // 统计答案, 当前贡献为 (results[i] - 1) / 2 上取整
                count += results[i] / 2;
            }
            return count;
        }


        /**
         * 中心扩散法(同LeetCode5)
         * @param s
         * @return
         */
        private int countSubstrings3(String s) {
            int len = s.length();
            int count = 0;
            char[] chars = s.toCharArray();
            for (int i = 0; i < len; i++) {
                count += expandAroundCenter(chars, i, i);
                count += expandAroundCenter(chars, i, i + 1);
            }
            return count;
        }


        /**
         * 动态规划(思路同LeetCode5)
         *
         * 1.原问题与子问题:
         *   判断字符串是否是回文串可以先判断头尾是否相同然后去掉头尾判断还是否是回文串
         *
         * 2.设计状态:
         *   f(i,j)表示以i开头以j结尾的字符串是否是回文串
         *
         * 3.状态转移方程
         *   f(i,j) = chars[i]== chars[j] && f(i+1, j-1) 其中 j-i >= 2
         *   f(i,i+1) = chars[i]== chars[j]
         *
         * 4.边界值
         *   f(i,i) = true;
         * @param s
         * @return
         */
        private int countSubstrings2(String s) {
            int len = s.length();
            int count = len;
            char[] chars = s.toCharArray();
            boolean[][] dp = new boolean[len][len]; // dp[i][j]表示以i开头,j结尾的子串是否是回文串
            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = true;
            }
            for (int subLen = 2; subLen <= len; subLen++) {
                for (int i = 0; i + subLen - 1 < len; i++) {
                    int j = i + subLen - 1;
                    if (j - i > 1) { // 子串长度大于2
                        dp[i][j] = (chars[i] == chars[j]) && dp[i + 1][j - 1];
                    } else { // 子串长度为2
                        dp[i][j] = (chars[i] == chars[j]);
                    }
                    if (dp[i][j]) count++;
                }
            }
            return count;
        }


        /**
         * 暴力法
         * 双指针判断每个子串是否是回文串
         * @param s
         * @return
         */
        private int countSubstrings1(String s) {
            int len = s.length();
            int count = len;
            char[] chars = s.toCharArray();
            for (int subLen = 2; subLen <= len; subLen++) {
                for (int i = 0; i + subLen - 1 < len; i++) {
                    int j = i + subLen - 1;
                    if (isPalindrome(chars, i, j)) count++;
                }
            }
            return count;
        }

        // 得到以left,right为中心的所有的回文串个数(left == right 奇, right == left + 1 偶)
        private int expandAroundCenter(char[] chars, int left, int right) {
            int count = 0;
            while (left >= 0 && right < chars.length && chars[left--] == chars[right++]) {
                count++;
            }
            return count;
        }

        private boolean isPalindrome(char[] chars, int left, int right) {
            while (left <= right) {
                if (chars[left++] != chars[right--]) return false;
            }
            return true;
        }

        public int countSubstrings(String s) {
            return countSubstrings4(s);
        }
    }
}
